import java.util.*;

/**
 * @Auther: wangliuyang
 * @Date: 2021/4/23 06:47
 * @Description: 15. 三数之和
 */
public class Solution_15 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new LinkedList<>();
        Arrays.sort(nums);
        int len = nums.length;
        for (int a = 0; a < len; a++) {
            int b = a + 1;
            int c = len - 1;
            while (b < c) {
                if (nums[a] + nums[b] + nums[c] == 0) {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(nums[a]);
                    list.add(nums[b]);
                    list.add(nums[c]);
                    ans.add(list);
                    while (b + 1 < len && nums[b] == nums[b + 1]) {
                        b++;
                    }
                    b++;
                }else if (nums[a] + nums[b] + nums[c] > 0) {
                    c--;
                }else {
                    while (b + 1 < len && nums[b] == nums[b + 1]) {
                        b++;
                    }
                    b++;
                }
            }
            while (a + 1 < len && nums[a] == nums[a + 1]) {
                a++;
            }
        }
        return ans;
    }
}
